package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         117,
		Discription: "将二叉树的每个节点指向右侧节点",
		Level:       2,
		Labels: map[string]int{
			"二叉树": 1,
		},
	})
}

func ConnectNext2(root *ds.Node) *ds.Node {
	upper := root
	for upper != nil {
		var nextUpper, curLower *ds.Node
		//利用上一层的next连接当前层的next
		//维护一个curLower指向当前待连接next的节点，每一层初始的curLower和nextUpper一样
		for upper != nil {
			if upper.Left != nil {
				if nextUpper == nil {
					nextUpper = upper.Left
				}
				if curLower == nil {
					curLower = upper.Left
				} else {
					curLower.Next = upper.Left
					curLower = curLower.Next
				}
			}

			if upper.Right != nil {
				if nextUpper == nil {
					nextUpper = upper.Right
				}
				if curLower == nil {
					curLower = upper.Right
				} else {
					curLower.Next = upper.Right
					curLower = curLower.Next
				}
			}

			upper = upper.Next
		}

		upper = nextUpper
	}

	return root
}
